Euler's Theorem

Theorem

For \(a, n \in \mathbb{Z}\) with \(\gcd(a, n) = 1\), we have that:

\[ a^{\varphi(n)} = 1 \pmod n\]

where \(\varphi\) is Euler's totient function.

Proof

This fact is just a special case of the fact that any group element to the power of group order is the identity.

Specifically, we have for any element \(a\) of the multiplicative group \(\mathbb{U}_n\), then

\[ a^{|\mathbb{U}_n|} = \mathrm{id}_{\mathbb{U}_n}.\]

Then, we know that \(a \in \mathbb{U}_n\) if and only if \(\gcd(a, n) = 1\), \(|\mathbb{U}_n| = \varphi(n)\) and that the identity of this group is the residue class of \(1\).